package com.guaoran.algorithm.stack;

import java.util.Stack;

/**
 * @Auth gucheng
 * @Desc 区间最大值
 * @From 字节跳动
 * @Date 2020/12/23 下午2:53
 */
public class MaximumRange {
    /**
     * 给定一段数组，求每个区间的最小值乘这段区间的和，输出每个区间得到的最大值。
     *
     * 　　样例输入：[1 2 6]，可能有以下几种情况：
     *
     * 　　[1]：结果为1*1=1；
     * 　　[2]：结果为2*2=4；
     * 　　[6]：结果为6*6=36；
     * 　　[1,2]：结果为1*(1+2)=3;
     * 　　[2,6]：结果为2*(2+6)=16;
     * 　　[1,2,6]：结果为1*(1+2+6)=9;
     * 　　最大值为36，输出36即可。
     */
    public static void main(String[] args) {
//        int [] numbers = {1,2,6};
        int [] numbers = {5,2,3,4,1};
        System.out.println(getMax(numbers));
    }

    private static int getMax(int[] numbers) {
        if(numbers == null || numbers.length == 0) return 0;

        int [] sum = new int[numbers.length + 1];
        for (int i = 1; i <= numbers.length; i++) {
            sum[i] = sum[i-1] + numbers[i-1];
        }

        int max = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < numbers.length; i++) {
            // 栈不为空，这里保证栈底是最小的元素
            while(!stack.isEmpty() && numbers[i] < numbers[stack.peek()]){
                int index = stack.pop();// 目前栈顶的元素下标
                int left = i;
                int right = i;
                if(stack.isEmpty()){
                    left = 0;
                } else {
                    left = index;
                }
                max = Math.max(max,numbers[index] * (sum[right] - sum[left]));
            }
            stack.push(i);
        }

        while(!stack.isEmpty()){
            int index = stack.pop();
            int left = numbers.length;
            int right = numbers.length;
            if(stack.isEmpty()){
                left = 0;
            } else {
                left = index;
            }
            max = Math.max(max,numbers[index] * (sum[right] - sum[left]));
        }
        return max;
    }
}
